package com.dkd.day202511;

import com.dkd.day20250616.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;


public class Solutiion8 {
    public static void main(String[] args) {
        //给你一个二叉树的根节点 root ， 检查它是否轴对称
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(3);
        System.out.println(isSymmetric(root));
    }

    public static boolean isSymmetric(TreeNode root) {
        //使用堆，堆内数据添加到列表，列表判断是否对称
        //代码正确，但是效率慢
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<TreeNode> list = new ArrayList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            //列表添加元素
            while (!stack.isEmpty()) {
                list.add(stack.pop());
            }
            //判断列表是否对称
            int n=list.size();
            for (int i = 0; i < n/2; i++) {
                //先判断是否是null
                if(list.get(i)==null) {
                    if(list.get(n-1-i)==null) {
                        continue;
                    }else{
                        return false;
                    }
                }
                if(list.get(n-1-i)==null) return false;
                if (list.get(i).val != list.get(n-1-i).val) return false;
            }
            //将列表的左右节点入栈
            for (int i = 0; i < n; i++) {
                if (list.get(i) != null) {
                    stack.push(list.get(i).left);
                    stack.push(list.get(i).right);
                }
            }
            list.clear();
        }
        return true;
    }

    public static boolean isSymmetric2(TreeNode root) {
        //递归解法
        return check(root.left, root.right);
    }

    public static boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }

    public boolean check2(TreeNode u, TreeNode v) {
        //官方递归，不是每层，而是每个节点
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(u);
        q.offer(v);
        while (!q.isEmpty()) {
            u = q.poll();
            v = q.poll();
            if (u == null && v == null) {
                continue;
            }
            if ((u == null || v == null) || (u.val != v.val)) {
                return false;
            }

            q.offer(u.left);
            q.offer(v.right);

            q.offer(u.right);
            q.offer(v.left);
        }
        return true;
    }
}
